package graph.test;

import graph.inter.CustGraph;
import graph.inter.UndirectedGraph;
import graph.undirectedgraph.algraph.AdjacencyListGraph;
import graph.undirectedgraph.mgraph.MatrixGraph;

public class GraphMain {
    public static final int MA = CustGraph.MA;

    public static void main(String[] args) {
//        graphTest();
//        primTest();
        shortPathTest();

    }

    public static void graphTest() {
        String[] vexs = {"A", "B", "C", "D", "E", "F", "G", "H", "I"};

        int[][] arc = {
                {0, 1, 0, 0, 0, 1, 0, 0, 0},
                {1, 0, 1, 0, 0, 0, 1, 0, 1},
                {0, 1, 0, 1, 0, 0, 0, 0, 1},
                {0, 0, 1, 0, 1, 0, 1, 1, 1},
                {0, 0, 0, 1, 0, 1, 0, 1, 0},
                {1, 0, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 1, 0, 1, 0, 1, 0},
                {0, 0, 0, 1, 1, 0, 1, 0, 0},
                {0, 1, 1, 1, 0, 0, 0, 0, 0}
        };
        CustGraph graph = new AdjacencyListGraph(vexs, arc);
        graph.dfsTraverse(3);
        System.out.println();
        graph.bfsTraverse(0);
    }

    public static void primTest() {
        String[] vexs = {"v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"};
        int[][] arc = {
                {0, 10, MA, MA, MA, 11, MA, MA, MA},
                {10, 0, 18, MA, MA, MA, 16, MA, 12},
                {MA, 18, 0, 22, MA, 24, MA, MA, 8},
                {MA, MA, 22, 0, 20, MA, MA, 16, 21},
                {MA, MA, MA, 20, 0, 26, MA, 7, MA},
                {11, MA, 24, MA, 26, 0, 17, MA, MA},
                {MA, 16, MA, MA, MA, 17, 0, 19, MA},
                {MA, MA, MA, 16, 7, MA, 19, 0, MA},
                {MA, 12, 8, 21, MA, MA, MA, MA, 0}
        };
        UndirectedGraph graph = new AdjacencyListGraph(vexs, arc);
        graph.miniSpanTreeKruskal();
    }

    public static void shortPathTest() {
        String[] vexs =      {"v0", "v1", "v2", "v3", "v4", "v5", "v6", "v7", "v8"};
        int[][] arc = {
                {0, 1, 5, MA, MA, MA, MA, MA, MA},
                {1, 0, 3, 7, 5, MA, MA, MA, MA},
                {5, 3, 0, MA, 1, 7, MA, MA, MA},
                {MA, 7, MA, 0, 2, MA, 3, MA, MA},
                {MA, 5, 1, 2, 0, 3, 6, 9, MA},
                {MA, MA, 7, MA, 3, 0, MA, 5, MA},
                {MA, MA, MA, 3, 6, MA, 0, 2, 7},
                {MA, MA, MA, MA, 9, 5, 2, 0, 4},
                {MA, MA, MA, MA, MA, MA, 7, 4, 0}
        };
        MatrixGraph graph = new MatrixGraph(vexs, arc);
        int[] path = new int[vexs.length];
        int[] dist = new int[vexs.length];
        graph.shortestPathDijstra(5, path, dist);
        System.out.println("end");
    }
}
